import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

public class test2 {
    //力扣 30. 串联所有单词的子串
    public static void main(String[] args) {

    }

    public static List<Integer> findSubstring(String s, String[] words) {
        List<Integer> ret = new ArrayList<>();
        //用于记录字典里字符串的出现次数
        Map<String, Integer> hash1 = new HashMap<>();
        for (String str : words) {
            //getOrDefault(str,0) 如果键有映射关系则返回它对应的值，否则返回0；
            hash1.put(str, hash1.getOrDefault(str, 0) + 1);
        }
        int len = words[0].length();
        int m = words.length;
        //这里的循环次数不能超过len，否则都是重复操作，应重点注意
        for (int i = 0; i < len; i++) {
            //记录滑动窗口里字符串的出现次数
            Map<String, Integer> hash2 = new HashMap<>();
            //这里的left和right的起始条件也要十分注意
            //判断条件也是细节，不能越界，也不能枚举到无用的值，把它当成一个个整体单词来看
            for (int left = i, right = i, count = 0; right + len <= s.length(); right += len) {
                String in = s.substring(right, right + len);
                //进窗口
                hash2.put(in, hash2.getOrDefault(in, 0) + 1);
                //维护count，可以看一下上一题
                if (hash2.get(in) <= hash1.getOrDefault(in, 0)) {
                    count++;
                }
                //判断条件
                if (right - left + 1 > len * m) {
                    String out = s.substring(left, left + len);
                    //维护count
                    if (hash2.get(out) <= hash1.getOrDefault(out, 0)) {
                        count--;
                    }
                    //出窗口
                    hash2.put(out, hash2.get(out) - 1);
                    left += len;
                }
                //更新结果
                if (count == m) {
                    ret.add(left);
                }

            }
        }
        return ret;
    }
}
